РЕФЕРАТ
Пояснювальна записка до курсової роботи містить 16 сторінок, 9 рисунків, 3 джерела літератури, 2 додатки.
Темою роботи є написання програми на XLisp, визначальною, чи є даний неорієнтований граф зв'язковим.
Метою роботи є набуття навичок і методів програмування досить складних завдань на мовах логічного програмування, а також підготовка до виконання дипломного проекту.
Ключові слова: програма, алгоритм, пошук, вершина, ребро, граф, зв'язаність, шлях, список, функція.
ЗМІСТ
Введення
1 Аналіз завдання
2 Обгрунтування вибору алгоритму і структур даних
3 Опис алгоритму
4 Обгрунтування набору тестів
Висновок
Список літератури
Додаток 1. Текст програми
Додаток 2. Результати роботи програми
ВСТУП
Двійкові дерева грають дуже важливу роль в теорії інформації.
Припустимо, що певна кількість повідомлень потрібно закодувати у вигляді кінцевих послідовностей різної довжини, що складаються з нулів і одиниць. Якщо ймовірності кодових слів задані, то найкращим вважається код, в якому середня довжина слів мінімальна в порівнянні з іншими розподілами ймовірності. Задачу про побудову такого оптимального коду дозволяє вирішити алгоритм Хаффмана.
Двійкові кодові дерева допускають інтерпретацію в рамках теорії пошуку. Кожній вершині при цьому зіставляється питання, відповісти на який можна або "так", або "ні". Стверджувальному і негативної відповіді відповідають два ребра, що виходять з вершини. "Опитування" завершується, коли вдається встановити те, що було потрібно. Таким чином, якщо комусь знадобиться взяти інтерв'ю у різних людей, і відповідь на чергове запитання буде залежати від заздалегідь невідомого відповіді на попереднє запитання, то план такого інтерв'ю можна представити у вигляді двійкового дерева.
Ще недавно однією з найбільш складних і утомливих завдань для радіоаматорів було конструювання друкованих схем.
Друкованої схемою називають платівку з якого-небудь діелектрика, на якій у вигляді металевих смужок витравлені доріжки. Перетинатися доріжки можуть тільки в певних точках, куди встановлюються необхідні елементи (діоди, тріоди, резистори й інші), їх перетин в інших місцях викличе замикання електричного кола.
У результаті вирішення цього завдання необхідно викреслити плоский граф, з вершинами у вказаних точках.
Можна навести безліч прикладів, незаперечно доводять практичну цінність теорії графів.
Темою роботи є написання програми на XLisp, визначальною, чи є даний неорієнтований граф зв'язковим. Метою роботи є набуття навичок і методів програмування досить складних завдань на мовах логічного програмування, а також підготовка до виконання дипломного проекту.
1 Аналіз завдання
У даній роботі необхідно написати програму мовою XLisp, визначальну, чи є даний неорієнтований граф зв'язковим. Для цього необхідно запрограмувати попередньо предикат (path XY), перевіряючий, чи існує шлях з вершини X в вершину Y.
Кажуть, що заданий неорієнтований граф G, якщо задані дві множини:
- Непорожня безліч V = {v 1 ,..., v n} - множина вершин графа;
- Безліч Q невпорядкованих пар (v i, v j), де v i, v j Î V. Це безліч називається безліччю ребер графа. Очевидно, що (v i, v j) Î Q Û (v j, v i) Î Q, причому це одне і те ж ребро.
Шляхом від v i до v j називається така послідовність ребер графа, що веде від v i до v j, в якій два сусідніх ребра мають загальну вершину і ніяке ребро не зустрічається двічі.
Дві вершини графа називаються зв'язковими, якщо в графі існує шлях з кінцями в цих вершинах, і незв'язними в іншому випадку.
Граф називається зв'язковим, якщо будь-які дві його вершини зв'язні, і незв'язних в іншому випадку.
2 Обгрунтування вибору алгоритму і структур даних
Для визначення зв'язності графа використовується пошук шляху від однієї вершини до іншої. Граф є зв'язковим, якщо всі вершини зв'язані між собою. Можна стверджувати, що граф є зв'язним, якщо одну з вершин можна з'єднати з усіма іншими шляхом. Алгоритм визначення зв'язності графа полягає в пошуку шляху від першої вершини до всіх інших. Якщо всі шляхи можна знайти - значить граф зв'язний.
Пошук шляху від однієї вершини до іншої буде виконуватися за алгоритмом пошуку в ширину. Схема алгоритму зображена на малюнку 2.1.
Рис.2.1 - Схема алгоритму пошуку в ширину
Пошук вершин, суміжних з новими вершинами виконується так:
а) Якщо список ребер порожній - вихід.
б) Береться перший ребро в списку ребер.
в) Якщо одна з вершин ребра знаходиться в списку нових вершин, а друга не входить ні в список нових вершин, ні в список знайдених вершин, то вершина додається в список суміжних вершин.
г) Видалити зі списку ребер перше ребро і перейти до пункту а.
Граф представляється двома множинами (списками): списком вершин і списком ребер. Кожне ребро - це список з двох вершин. Даний вибір обгрунтовується тим, що списки є основним способом зображення багатьох даних.
3 Опис алгоритму
Були розроблені наступні функції (текст програми приведений у додатку 1).
Функція smezver (xy snaid snov) - визначає, чи є вершина y суміжній з однією з нових вершин (x - входить в список нових вершин, y - не входить до списків нових і знайдених вершин).
Параметри:
- X - перша вершина ребра;
- Y - друга вершина ребра;
- Snaid - список знайдених вершин;
- Snov - список нових вершин.
Функція smez (snaid snov sreb) - пошук суміжних з новими вершинами вершин.
Параметри:
- Snaid - список знайдених вершин;
- Snov - список нових вершин;
- Sreb - список ребер.
Функція shir (snaid snov y sreb) - пошук в ширину шляху.
Параметри:
- Snaid - список знайдених вершин;
- Snov - список нових знайдених вершин;
- Y - вершина для пошуку;
- Sreb - список ребер.
Функція path (xy sreb) - пошук шляху від вершини x до вершини y.
Параметри:
- X - перша вершина;
- Y - друга вершина;
- Sreb - список ребер.
Функція perebor (fver sver sreb) - перебір вершин і пошук шляху від першої вершини до всіх інших.
Параметри:
- Fver - перша вершина;
- Sver - список вершин:
- Sreb - список ребер.
Функція svgraf (sver sreb) - визначення пов'язаності графа.
Параметри:
- Sver - список вершин;
- Sreb - список ребер.
4 Обгрунтування набору тестів
Під час тестування використовуються наступні тести:
Рис.4.1 - Тест 1. Зв'язаний граф
Рис. 4.2 - Тест 2. Зв'язаний граф
Рис. 4.3 - Тест 3. Незв'язаний граф
Рис. 4.4 - Тест 4. Зв'язаний граф
Рис. 4.5 - Тест 5. Незв'язаний граф
Рис. 4.6 - Тест 6. Зв'язаний граф
Рис. 4.7 - Тест 7. Незв'язаний граф
Рис. 4.8 - Тест 8. Незв'язаний граф
Перераховані тести являють собою різні вхідні дані, які дозволяють повністю перевірити роботу програми.
При тестуванні всі тести були виконані успішно. Результати роботи програми наведені в додатку 2.
ВИСНОВОК
У даній роботі написана програма на XLisp, визначальною, чи є даний неорієнтований граф зв'язковим.
Усі поставлені цілі виконані: придбано навички і методи програмування досить складних завдань на мовах логічного програмування, а також проведена підготовка до виконання дипломного проекту.
Програма налагоджена й протестована.
СПИСОК ЛІТЕРАТУРИ
1 Лутай В.М. Програмування на мовах Лісп і Пролог. ТРТУ, 1998.
2 Філд А., Харрісон П. Функціональне програмування. - М.: Світ, 1993.
3 Уілсон Р. Введення в теоpію гpафов. - М.: Миp, 1977.
ДОДАТОК 1
Текст програми
; Суміжна вершина (перша вершина ребра, друга вершина ребра,
; Список знайдених вершин, список нових вершин)
(Defun smezver (xy snaid snov)
(Cond
((Not (member x snov)) nil); x не є новою вершиною
((Member y snov) nil); y є новою вершиною
((Member y snaid) nil); y є раніше знайденої вершиною
(Tt))); вершина є новою суміжної вершиною
; Пошук суміжних вершин (список знайдених вершин, список нових вершин, список ребер)
(Defun smez (snaid snov sreb)
(Cond
((Null sreb) nil); кінець пошуку
((Smezver (caar sreb) (cadar sreb) snaid snov); суміжна вершина
(Cons (cadar sreb) (smez snaid snov (cdr sreb)))); додавання до списку
((Smezver (cadar sreb) (caar sreb) snaid snov); суміжна вершина
(Cons (caar sreb) (smez snaid snov (cdr sreb)))); додавання до списку
(T (smez snaid snov (cdr sreb ))))); пропуск ребра
; Пошук в ширину (список знайдених вершин, список нових знайдених вершин,
; Вершина для пошуку, список ребер)
(Defun shir (snaid snov y sreb)
(Cond
((Null snov) nil); не знайдено жодної нової вершини
((Member y snov) t); вершина знайдена
(T (shir (append snaid snov) (smez snaid snov sreb) y sreb)))); додавання нових вершин
; Пошук шляху (перша вершина, друга вершина, список ребер)
(Defun path (xy sreb)
(Shir nil (list x) y sreb)); пошук в ширину
; Перебір вершин (перша вершина, список вершин, список ребер)
(Defun perebor (fver sver sreb)
(Cond
((Null sver) t); кінець перебору
((Path fver (car sver) sreb) (perebor fver (cdr sver) sreb)); шлях знайдений
(T nil))); немає шляху
; Визначення пов'язаності графа (список вершин, список ребер)
(Defun svgraf (sver sreb)
(Perebor (car sver) (cdr sver) sreb)); перебір вершин і пошук шляху від першої вершини до всіх інших
ДОДАТОК 2
Результати роботи програми
Тест: 1
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v2 v3) (v3 v4)))
Результат: Т
Тест: 2
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v2 v4) (v2 v3) (v3 v4) (v1 v4) (v3 v4)))
Результат: T
Тест: 3
Вираз: (svgraf '(v1 v2 v3 v4 v5 v6 v7)' ((v1 v2) (v2 v3) (v1 v3) (v4 v5) (v4 v7) (v5 v6) (v6 v7)))
Результат: NIL
Тест: 4
Вираз: (svgraf '(v1 v2 v3 v4 v5 v6)' ((v1 v7) (v2 v7) (v3 v7) (v4 v7) (v5 v7) (v6 v7) (v1 v1) (v2 v2) (v3 v3 ) (v4 v4) (v5 v5) (v6 v6)))
Результат: T
Тест: 5
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v1 v2) (v3 v4) (v3 v4)))
Результат: NIL
Тест: 6
Вираз: (svgraf '(v1) nil)
Результат: T
Тест: 7
Вираз: (svgraf '(v1 v2 v3) nil)
Результат: NIL
Тест: 8
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v2 v3) (v3 v1)))
Результат: NIL
Пояснювальна записка до курсової роботи містить 16 сторінок, 9 рисунків, 3 джерела літератури, 2 додатки.
Темою роботи є написання програми на XLisp, визначальною, чи є даний неорієнтований граф зв'язковим.
Метою роботи є набуття навичок і методів програмування досить складних завдань на мовах логічного програмування, а також підготовка до виконання дипломного проекту.
Ключові слова: програма, алгоритм, пошук, вершина, ребро, граф, зв'язаність, шлях, список, функція.
ЗМІСТ
Введення
1 Аналіз завдання
2 Обгрунтування вибору алгоритму і структур даних
3 Опис алгоритму
4 Обгрунтування набору тестів
Висновок
Список літератури
Додаток 1. Текст програми
Додаток 2. Результати роботи програми
ВСТУП
Двійкові дерева грають дуже важливу роль в теорії інформації.
Припустимо, що певна кількість повідомлень потрібно закодувати у вигляді кінцевих послідовностей різної довжини, що складаються з нулів і одиниць. Якщо ймовірності кодових слів задані, то найкращим вважається код, в якому середня довжина слів мінімальна в порівнянні з іншими розподілами ймовірності. Задачу про побудову такого оптимального коду дозволяє вирішити алгоритм Хаффмана.
Двійкові кодові дерева допускають інтерпретацію в рамках теорії пошуку. Кожній вершині при цьому зіставляється питання, відповісти на який можна або "так", або "ні". Стверджувальному і негативної відповіді відповідають два ребра, що виходять з вершини. "Опитування" завершується, коли вдається встановити те, що було потрібно. Таким чином, якщо комусь знадобиться взяти інтерв'ю у різних людей, і відповідь на чергове запитання буде залежати від заздалегідь невідомого відповіді на попереднє запитання, то план такого інтерв'ю можна представити у вигляді двійкового дерева.
Ще недавно однією з найбільш складних і утомливих завдань для радіоаматорів було конструювання друкованих схем.
Друкованої схемою називають платівку з якого-небудь діелектрика, на якій у вигляді металевих смужок витравлені доріжки. Перетинатися доріжки можуть тільки в певних точках, куди встановлюються необхідні елементи (діоди, тріоди, резистори й інші), їх перетин в інших місцях викличе замикання електричного кола.
У результаті вирішення цього завдання необхідно викреслити плоский граф, з вершинами у вказаних точках.
Можна навести безліч прикладів, незаперечно доводять практичну цінність теорії графів.
Темою роботи є написання програми на XLisp, визначальною, чи є даний неорієнтований граф зв'язковим. Метою роботи є набуття навичок і методів програмування досить складних завдань на мовах логічного програмування, а також підготовка до виконання дипломного проекту.
1 Аналіз завдання
У даній роботі необхідно написати програму мовою XLisp, визначальну, чи є даний неорієнтований граф зв'язковим. Для цього необхідно запрограмувати попередньо предикат (path XY), перевіряючий, чи існує шлях з вершини X в вершину Y.
Кажуть, що заданий неорієнтований граф G, якщо задані дві множини:
- Непорожня безліч V = {v 1 ,..., v n} - множина вершин графа;
- Безліч Q невпорядкованих пар (v i, v j), де v i, v j Î V. Це безліч називається безліччю ребер графа. Очевидно, що (v i, v j) Î Q Û (v j, v i) Î Q, причому це одне і те ж ребро.
Шляхом від v i до v j називається така послідовність ребер графа, що веде від v i до v j, в якій два сусідніх ребра мають загальну вершину і ніяке ребро не зустрічається двічі.
Дві вершини графа називаються зв'язковими, якщо в графі існує шлях з кінцями в цих вершинах, і незв'язними в іншому випадку.
Граф називається зв'язковим, якщо будь-які дві його вершини зв'язні, і незв'язних в іншому випадку.
2 Обгрунтування вибору алгоритму і структур даних
Для визначення зв'язності графа використовується пошук шляху від однієї вершини до іншої. Граф є зв'язковим, якщо всі вершини зв'язані між собою. Можна стверджувати, що граф є зв'язним, якщо одну з вершин можна з'єднати з усіма іншими шляхом. Алгоритм визначення зв'язності графа полягає в пошуку шляху від першої вершини до всіх інших. Якщо всі шляхи можна знайти - значить граф зв'язний.
Пошук шляху від однієї вершини до іншої буде виконуватися за алгоритмом пошуку в ширину. Схема алгоритму зображена на малюнку 2.1.
Рис.2.1 - Схема алгоритму пошуку в ширину
Пошук вершин, суміжних з новими вершинами виконується так:
а) Якщо список ребер порожній - вихід.
б) Береться перший ребро в списку ребер.
в) Якщо одна з вершин ребра знаходиться в списку нових вершин, а друга не входить ні в список нових вершин, ні в список знайдених вершин, то вершина додається в список суміжних вершин.
г) Видалити зі списку ребер перше ребро і перейти до пункту а.
Граф представляється двома множинами (списками): списком вершин і списком ребер. Кожне ребро - це список з двох вершин. Даний вибір обгрунтовується тим, що списки є основним способом зображення багатьох даних.
3 Опис алгоритму
Були розроблені наступні функції (текст програми приведений у додатку 1).
Функція smezver (xy snaid snov) - визначає, чи є вершина y суміжній з однією з нових вершин (x - входить в список нових вершин, y - не входить до списків нових і знайдених вершин).
Параметри:
- X - перша вершина ребра;
- Y - друга вершина ребра;
- Snaid - список знайдених вершин;
- Snov - список нових вершин.
Функція smez (snaid snov sreb) - пошук суміжних з новими вершинами вершин.
Параметри:
- Snaid - список знайдених вершин;
- Snov - список нових вершин;
- Sreb - список ребер.
Функція shir (snaid snov y sreb) - пошук в ширину шляху.
Параметри:
- Snaid - список знайдених вершин;
- Snov - список нових знайдених вершин;
- Y - вершина для пошуку;
- Sreb - список ребер.
Функція path (xy sreb) - пошук шляху від вершини x до вершини y.
Параметри:
- X - перша вершина;
- Y - друга вершина;
- Sreb - список ребер.
Функція perebor (fver sver sreb) - перебір вершин і пошук шляху від першої вершини до всіх інших.
Параметри:
- Fver - перша вершина;
- Sver - список вершин:
- Sreb - список ребер.
Функція svgraf (sver sreb) - визначення пов'язаності графа.
Параметри:
- Sver - список вершин;
- Sreb - список ребер.
4 Обгрунтування набору тестів
Під час тестування використовуються наступні тести:
Рис.4.1 - Тест 1. Зв'язаний граф
Рис. 4.2 - Тест 2. Зв'язаний граф
Рис. 4.3 - Тест 3. Незв'язаний граф
Рис. 4.4 - Тест 4. Зв'язаний граф
Рис. 4.5 - Тест 5. Незв'язаний граф
Рис. 4.6 - Тест 6. Зв'язаний граф
Рис. 4.7 - Тест 7. Незв'язаний граф
Рис. 4.8 - Тест 8. Незв'язаний граф
Перераховані тести являють собою різні вхідні дані, які дозволяють повністю перевірити роботу програми.
При тестуванні всі тести були виконані успішно. Результати роботи програми наведені в додатку 2.
ВИСНОВОК
У даній роботі написана програма на XLisp, визначальною, чи є даний неорієнтований граф зв'язковим.
Усі поставлені цілі виконані: придбано навички і методи програмування досить складних завдань на мовах логічного програмування, а також проведена підготовка до виконання дипломного проекту.
Програма налагоджена й протестована.
СПИСОК ЛІТЕРАТУРИ
1 Лутай В.М. Програмування на мовах Лісп і Пролог. ТРТУ, 1998.
2 Філд А., Харрісон П. Функціональне програмування. - М.: Світ, 1993.
3 Уілсон Р. Введення в теоpію гpафов. - М.: Миp, 1977.
ДОДАТОК 1
Текст програми
; Суміжна вершина (перша вершина ребра, друга вершина ребра,
; Список знайдених вершин, список нових вершин)
(Defun smezver (xy snaid snov)
(Cond
((Not (member x snov)) nil); x не є новою вершиною
((Member y snov) nil); y є новою вершиною
((Member y snaid) nil); y є раніше знайденої вершиною
(Tt))); вершина є новою суміжної вершиною
; Пошук суміжних вершин (список знайдених вершин, список нових вершин, список ребер)
(Defun smez (snaid snov sreb)
(Cond
((Null sreb) nil); кінець пошуку
((Smezver (caar sreb) (cadar sreb) snaid snov); суміжна вершина
(Cons (cadar sreb) (smez snaid snov (cdr sreb)))); додавання до списку
((Smezver (cadar sreb) (caar sreb) snaid snov); суміжна вершина
(Cons (caar sreb) (smez snaid snov (cdr sreb)))); додавання до списку
(T (smez snaid snov (cdr sreb ))))); пропуск ребра
; Пошук в ширину (список знайдених вершин, список нових знайдених вершин,
; Вершина для пошуку, список ребер)
(Defun shir (snaid snov y sreb)
(Cond
((Null snov) nil); не знайдено жодної нової вершини
((Member y snov) t); вершина знайдена
(T (shir (append snaid snov) (smez snaid snov sreb) y sreb)))); додавання нових вершин
; Пошук шляху (перша вершина, друга вершина, список ребер)
(Defun path (xy sreb)
(Shir nil (list x) y sreb)); пошук в ширину
; Перебір вершин (перша вершина, список вершин, список ребер)
(Defun perebor (fver sver sreb)
(Cond
((Null sver) t); кінець перебору
((Path fver (car sver) sreb) (perebor fver (cdr sver) sreb)); шлях знайдений
(T nil))); немає шляху
; Визначення пов'язаності графа (список вершин, список ребер)
(Defun svgraf (sver sreb)
(Perebor (car sver) (cdr sver) sreb)); перебір вершин і пошук шляху від першої вершини до всіх інших
ДОДАТОК 2
Результати роботи програми
Тест: 1
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v2 v3) (v3 v4)))
Результат: Т
Тест: 2
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v2 v4) (v2 v3) (v3 v4) (v1 v4) (v3 v4)))
Результат: T
Тест: 3
Вираз: (svgraf '(v1 v2 v3 v4 v5 v6 v7)' ((v1 v2) (v2 v3) (v1 v3) (v4 v5) (v4 v7) (v5 v6) (v6 v7)))
Результат: NIL
Тест: 4
Вираз: (svgraf '(v1 v2 v3 v4 v5 v6)' ((v1 v7) (v2 v7) (v3 v7) (v4 v7) (v5 v7) (v6 v7) (v1 v1) (v2 v2) (v3 v3 ) (v4 v4) (v5 v5) (v6 v6)))
Результат: T
Тест: 5
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v1 v2) (v3 v4) (v3 v4)))
Результат: NIL
Тест: 6
Вираз: (svgraf '(v1) nil)
Результат: T
Тест: 7
Вираз: (svgraf '(v1 v2 v3) nil)
Результат: NIL
Тест: 8
Вираз: (svgraf '(v1 v2 v3 v4)' ((v1 v2) (v2 v3) (v3 v1)))
Результат: NIL